package 剑指offer;

public class p49丑数 {
    public int nthUglyNumber(int n) {
        //动态规划
        int[] dp=new int[n];
        dp[0]=1;
        int index2=0,index3=0,index5=0;

        for (int i = 1; i <n ; i++) {
            int a=dp[index2]*2;
            int b=dp[index3]*3;
            int c=dp[index5]*5;

            dp[i]=Math.min(Math.min(a,b) , c);

            if (dp[i]==a) index2++;
            if (dp[i]==b) index3++;
            if (dp[i]==c) index5++;
        }
        return dp[n-1];
    }


    public int nthUglyNumber1(int n) {
        //三指针
        int[] arr=new int[n];
        arr[0]=1;

        int index2=0;
        int index3=0;
        int index5=0;

        for (int i = 1; i <n; i++) {
            arr[i]=Math.min( Math.min(arr[index2]*2,arr[index3]*3) , arr[index5]*5 );

            //三个指针谁前进???
            if (arr[i]==arr[index2]*2) {
                index2++;
            }
            if (arr[i]==arr[index3]*3) {
                index3++;
            }
            if (arr[i]==arr[index5]*5) {
                index5++;
            }
        }

        return arr[n-1];
    }
}
